/*
# File    :   union_find_set.c
# Author  :   Zhihang
# Date    :   Sun, May 26, 2019 10:52:52 PM
*/

#include <stdio.h>
static const int true = 1;
static const int false = 0;

#define N 5 //数据数量
//const int n=5; 
int father[N]; //父亲节点
int zi[N]; //一个数据的层数

int parents(int v)
{ 
    //找祖宗节点
    while(v!=father[v]){
        father[v]=father[father[v]];
        v=father[v];
    }
    return v;
}

void _union(int v,int w)
{ 
    //合并
    int parents_v=parents(v); //找到祖宗
    int parents_w=parents(w);

    if(zi[parents_v]>zi[parents_w]){             //看哪个祖宗的子孙多（层数） 
        father[parents_w]=father[parents_w];
    }   
    else if(zi[parents_w]>zi[parents_v]){
        father[parents_v]=parents_w;    
    }
    else if(zi[parents_v]==zi[parents_w]){
        father[parents_v]=parents_w;
        zi[parents_v]++;    
    }
}

int find(int v,int w)
{ 
    //查找两个点是否连着了

    if(parents(v)==parents(w))
    { //找到两个点的祖宗节点，
        return true; //如果一样返回 真

    }
    else{ //否则返回 假
        return false;
    }
}


int main(int argc, char *argv[])
{
    int i;
    //初始化
    for(i=0; i <N; i++){
        father[i] =i;
        zi[i] = 0;
    }

    //测试
    _union(1,5);
    printf("union(1,5)\n");
    _union(2,5);
    printf("union(2,5)\n");
    _union(1,3);
    printf("union(1,3)\n");

    printf("find(2, 4),%d(0 is ok)\n", find(2, 4));
    _union(3,4);
    printf("union(3,4)\n");
    printf("find(2, 4),%d(1 is ok)\n", find(2, 4));

    return 0;
}
